[큐] 백준 2164번

문제

N장의 카드가 존재 (순서가 순차적으로 카드개수만큼 존재)

1. 1에서 N까지 번호가 존재
2. 아래 동작으로 계속 반복 후 마지막 수를 출력 
   ( 순서 )
       > 가장 위에 있는 카드를 바닥에 버림
       > 그다음 가장 위에있는 카드를 마지막으로 옮김
       > 이걸 반복

정수 N ( 1 <= N <= 500,000 )이 주어진다.

문제분석

• 가장 위에있는 카드를 가장 마지막으로 이동 시키는 작업 ( -> Queue의 이해도 확인 )
• 선입선출을 생각하여 문제 풀기

슈도코드

N개 입력 받기
for( 카드의 개수 ){
    큐에 카드 저장
}
 
while( 카드 1장이 남을때까지 ){
     맨위의 카드를 버림
     맨위의 카드를 가장 아래의 카드 밑으로 이동
}
 
마지막으로 남은 카드 출력

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(buf.readLine());
        
        Queue<Integer> q = new LinkedList<>();
 
        for (int i =1; i<= size; i++){
            q.add(i);
        }
 
        while(q.size() > 1){
            q.poll();
            q.add(q.poll());
        }
        System.out.println(q.poll());
        
    }
}

---

관련 문서

• (자료구조) [Queue] 클래스 설명 및 메서드 — 이 문제에서 사용한 Queue 인터페이스(add/poll)의 메서드 정리